home *** CD-ROM | disk | FTP | other *** search
/ Gold Medal Software 2 / Gold Medal Software Volume 2 (Gold Medal) (1994).iso / archive / ntzip.arj / IMPLODE.C < prev    next >
C/C++ Source or Header  |  1992-03-26  |  9KB  |  287 lines
  1. /*
  2.  
  3.  Copyright (C) 1990,1991 Mark Adler, Richard B. Wales, and Jean-loup Gailly.
  4.  Permission is granted to any individual or institution to use, copy, or
  5.  redistribute this software so long as all of the original files are included
  6.  unmodified, that it is not sold for profit, and that this copyright notice
  7.  is retained.
  8.  
  9. */
  10.  
  11. /*
  12.  *  implode.c by Richard B. Wales.
  13.  *
  14.  *  PURPOSE
  15.  *
  16.  *      Compress an input file using the ZIP "implosion" method.
  17.  *
  18.  *  DISCUSSION
  19.  *
  20.  *      The "implosion" algorithm is a composite of (1) OPM/L compres-
  21.  *      sion within a sliding window, and (2) variable-length binary
  22.  *      encoding of various parts of the OPM/L output.
  23.  *
  24.  *      For a detailed treatment of OPM/L compression, see the source
  25.  *      file "im_lmat.c".
  26.  *
  27.  *      For a detailed treatment of variable-length binary encoding,
  28.  *      see the source file "im_ctree.c".
  29.  *
  30.  *      Since Pass Two (binary encoding) depends on a statistical anal-
  31.  *      ysis of the entire output of Pass One (OPM/L compression), the
  32.  *      Pass One output is saved in a temporary file and re-read for
  33.  *      Pass Two.  Implosion is thus a two-pass algorithm.
  34.  *
  35.  *      An outline of the algorithm follows:
  36.  *
  37.  *      (1) The entire input file is read and compressed via the OPM/L
  38.  *          technique.  The OPM/L output is saved in a temporary file.
  39.  *
  40.  *      (2) The compressed info from (1) is analyzed, and various fre-
  41.  *          quency counts are tallied.
  42.  *
  43.  *      (3) Based on the frequency counts, a decision is made as to
  44.  *          whether or not the "literal" characters (those not matched
  45.  *          in earlier parts of the input) should be represented via a
  46.  *          binary code tree or left "as is".  If there are not very
  47.  *          many literal characters, or if their frequency distribution
  48.  *          is fairly even, the number of bits saved through coding may
  49.  *          be exceeded by the amount of info which must be included to
  50.  *          describe the tree.
  51.  *
  52.  *      (4) The temporary file from (1) is re-read.  The information is
  53.  *          further compressed via the binary code trees, and the result
  54.  *          is sent to the ZIP output file.
  55.  *
  56.  *  REFERENCES
  57.  *
  58.  *      APPNOTE.TXT documentation file in PKZIP 1.10 distribution.
  59.  *
  60.  *      See also references in the "im_lmat.c" and "im_ctree.c" source
  61.  *      files.
  62.  *
  63.  *  INTERFACE
  64.  *
  65.  *      int imp_setup (long filesize, int pack_level)
  66.  *          Initialize the "implode" routines for a new file.
  67.  *
  68.  *      int imp_p1 (char *buf, int count)
  69.  *          Process "count" input characters pointed to by "buf".  This
  70.  *          routine is called as many times as needed to process the
  71.  *          entire input file.  There is no upper limit on "count".
  72.  *
  73.  *      int imp_size (long *size, char *opts)
  74.  *          Terminate processing of the input file, and return the com-
  75.  *          pressed size ("size") and implosion option flags ("opts").
  76.  *
  77.  *      int imp_p2 (FILE *outfp)
  78.  *          Output the entire compressed file -- including S-F trees and
  79.  *          data -- to the ZIP output file "outfp".
  80.  *
  81.  *      int imp_clear (void)
  82.  *          Clean up after processing and outputting a file.  This rou-
  83.  *          tine may be called at any time to abort further processing.
  84.  *
  85.  *      All the above routines return zero if successful, or a non-zero
  86.  *      value if there was an error.
  87.  */
  88.  
  89. #include "implode.h"
  90. #include "ziperr.h"
  91.  
  92.  
  93. /***********************************************************************
  94.  *
  95.  * Error return codes for the main ZIP program.
  96.  * Most of these are in "ziperr.h".
  97.  */
  98.  
  99. #define ZE_MAP(err) \
  100.         ( ((err) == IM_OK)      ? ZE_OK \
  101.         : ((err) == IM_NOMEM)   ? ZE_MEM \
  102.         : ((err) == IM_IOERR)   ? ZE_TEMP \
  103.                                 : (fprintf(stderr,"\nZE_MAP(%d)",(err)), \
  104.                                     ZE_LOGIC))
  105.  
  106.  
  107. /***********************************************************************
  108.  *
  109.  * State variable for the implosion routines.
  110.  */
  111.  
  112. #define IMP_SETUP       0       /* need to do "imp_setup" */
  113. #define IMP_P1          1       /* setup done, ready for Pass 1 */
  114. #define IMP_P2          2       /* Pass 1 done, ready for Pass 2 */
  115. #define IMP_CLEAR       3       /* Pass 2 done, ready for "imp_clear" */
  116.  
  117. local int imp_state = IMP_SETUP;
  118.  
  119.  
  120. /***********************************************************************
  121.  *
  122.  * Global variables.
  123.  */
  124.  
  125. FDATA fd;
  126.  
  127.  
  128. /***********************************************************************
  129.  *
  130.  * Set up for performing implosion on a new file.
  131.  */
  132.  
  133. int
  134. imp_setup (filesize, pack_level)
  135.     long filesize;  /* input file size */
  136.     int pack_level; /* 0 = best speed, 9 = best compression, other = default */
  137. {
  138.     ImpErr retcode;
  139.     extern char *tempname();
  140.  
  141.     if (imp_state != IMP_SETUP)
  142.     {   fprintf (stderr, "\nimp_setup called with wrong state %d",
  143.                  imp_state);
  144.         return ZE_LOGIC;
  145.     }
  146.     imp_state = IMP_P1;
  147.  
  148.     /* Set up the initial parameters. Use an 8K window if the input
  149.      * file is greater than or equal to 5.5K, a 4K window otherwise.
  150.      */
  151.     fd.fd_bufsize = 8192;
  152.     if (filesize < 5632) fd.fd_bufsize = 4096;
  153.  
  154.     fd.fd_strsize = 320;
  155.     fd.fd_nbits   = (fd.fd_bufsize == 4096) ? 6 : 7;
  156.  
  157.     /* Create a temporary file for the Pass One output. */
  158.     fd.fd_temp = topen ('I');
  159.     if (fd.fd_temp == NULL)
  160.         return ZE_MEM;
  161.  
  162.     /*
  163.      * Initialize the "longest match" routines.
  164.      * "ct_init" is called at this point because the "lm_input" routine
  165.      * (called in "imp_p1") calls the "ct_tally" routine.
  166.      */
  167.     retcode = lm_init (pack_level);
  168.     if (retcode != IM_OK) return ZE_MAP (retcode);
  169.     retcode = ct_init ();
  170.     return ZE_MAP (retcode);
  171. }
  172.  
  173.  
  174. /***********************************************************************
  175.  *
  176.  * Feed characters to the implosion computation.
  177.  * This routine is called as many times as needed, until the entire
  178.  * input file has been processed.
  179.  */
  180.  
  181. int
  182. imp_p1 (buf, count)
  183.     char *buf;                  /* input characters */
  184.     int   count;                /* character count */
  185. {   ImpErr retcode;
  186.  
  187.     if (imp_state != IMP_P1)
  188.     {   fprintf (stderr, "\nimp_p1 called with wrong state %d",
  189.                  imp_state);
  190.         return ZE_LOGIC;
  191.     }
  192.  
  193.     if (buf == NULL || count < 0)
  194.     {   fprintf (stderr, "\nimp_p1 called with bad arguments");
  195.         return ZE_LOGIC;
  196.     }
  197.     retcode = lm_input ((U_CHAR *) buf, (U_INT) count);
  198.     return ZE_MAP (retcode);
  199. }
  200.  
  201.  
  202. /***********************************************************************
  203.  *
  204.  * Terminate processing of input for this file, and determine the size
  205.  * this file will have if it is imploded.  Also, find out whether two
  206.  * or three S-F trees will be used (needed for directory entries).
  207.  */
  208.  
  209. int
  210. imp_size (size, opts)
  211.     long *size;                 /* imploded size */
  212.     char *opts;                 /* implosion option info */
  213. {   ImpErr retcode;
  214.  
  215.     if (imp_state != IMP_P1)
  216.     {   fprintf (stderr, "\nimp_size called with wrong state %d",
  217.                  imp_state);
  218.         return ZE_LOGIC;
  219.     }
  220.     imp_state = IMP_P2;
  221.  
  222.     if (size == NULL || opts == NULL)
  223.     {   fprintf (stderr, "\nimp_size called with bad arguments");
  224.         return ZE_LOGIC;
  225.     }
  226.     retcode = lm_windup ();
  227.     if (retcode != IM_OK) return ZE_MAP (retcode);
  228.     retcode = ct_mktrees ();
  229.     if (retcode != IM_OK) return ZE_MAP (retcode);
  230.     *size = fd.fd_clen;
  231.     *opts = (char)(((fd.fd_bufsize == 8192) ? 0x02 : 0)
  232.           | ((fd.fd_method == LITERAL_TREE) ? 0x04 : 0));
  233.     return ZE_OK;
  234. }
  235.  
  236.  
  237. /***********************************************************************
  238.  *
  239.  * Output the imploded version of the file (but not the file directory
  240.  * info) to the ZIP file.
  241.  */
  242.  
  243. int
  244. imp_p2 (outfp)
  245.     FILE *outfp;                        /* output (ZIP) file */
  246. {   ImpErr retcode;
  247.  
  248.     if (imp_state != IMP_P2)
  249.     {   fprintf (stderr, "\nimp_p2 called with wrong state %d",
  250.                  imp_state);
  251.         return ZE_LOGIC;
  252.     }
  253.     imp_state = IMP_CLEAR;
  254.  
  255.     if (outfp == NULL)
  256.     {   fprintf (stderr, "\nimp_p2 called with bad arguments");
  257.         return ZE_LOGIC;
  258.     }
  259.     retcode = ct_wrtrees (outfp);
  260.     if (retcode != IM_OK) return ZE_MAP (retcode);
  261.     retcode = ct_wrdata (outfp);
  262.     if (retcode != IM_OK) return ZE_MAP (retcode);
  263.     fflush (outfp);
  264.     if (ferror (outfp)) return ZE_TEMP;
  265.     return ZE_OK;
  266. }
  267.  
  268.  
  269. /***********************************************************************
  270.  *
  271.  * Clean up after doing an implosion.
  272.  * This routine may also be called at any time to abort an implosion.
  273.  */
  274.  
  275. int
  276. imp_clear ()
  277. {   (void) lm_windup ();
  278.     if (fd.fd_temp != NULL)
  279.         (void) tclose (fd.fd_temp);
  280.     (void) ct_windup ();
  281.     imp_state = IMP_SETUP;
  282.     return ZE_OK;
  283. }
  284.  
  285.  
  286. /**********************************************************************/
  287.